{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.743801652892562"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = ['a', 'b', 'c', 'd', 'b', 'c', 'a', 'b', 'c', 'd', 'a']\n",
    "def gini(nums):\n",
    "    probs = [nums.count(i)/len(nums) for i in set(nums)]\n",
    "    gini = sum([p*(1-p) for p in probs])\n",
    "    return gini\n",
    "\n",
    "gini(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>humility</th>\n",
       "      <th>outlook</th>\n",
       "      <th>temp</th>\n",
       "      <th>windy</th>\n",
       "      <th>play</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>hot</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>hot</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>high</td>\n",
       "      <td>overcast</td>\n",
       "      <td>hot</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>high</td>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>cool</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>cool</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>normal</td>\n",
       "      <td>overcast</td>\n",
       "      <td>cool</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>mild</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>normal</td>\n",
       "      <td>sunny</td>\n",
       "      <td>cool</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>normal</td>\n",
       "      <td>sunny</td>\n",
       "      <td>mild</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>high</td>\n",
       "      <td>overcast</td>\n",
       "      <td>mild</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>normal</td>\n",
       "      <td>overcast</td>\n",
       "      <td>hot</td>\n",
       "      <td>FALSE</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>high</td>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>TRUE</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   humility   outlook  temp  windy play\n",
       "0      high     sunny   hot  FALSE   no\n",
       "1      high     sunny   hot   TRUE   no\n",
       "2      high  overcast   hot  FALSE  yes\n",
       "3      high     rainy  mild  FALSE  yes\n",
       "4    normal     rainy  cool  FALSE  yes\n",
       "5    normal     rainy  cool   TRUE   no\n",
       "6    normal  overcast  cool   TRUE  yes\n",
       "7      high     sunny  mild  FALSE   no\n",
       "8    normal     sunny  cool  FALSE  yes\n",
       "9    normal     rainy  mild  FALSE  yes\n",
       "10   normal     sunny  mild   TRUE  yes\n",
       "11     high  overcast  mild   TRUE  yes\n",
       "12   normal  overcast   hot  FALSE  yes\n",
       "13     high     rainy  mild   TRUE   no"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.read_csv('./example_data.csv', dtype={'windy': 'str'})\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4591836734693877"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(df['play'].tolist())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_dataframe(data, col):\n",
    "    '''\n",
    "    function: split pandas dataframe to sub-df based on data and column.\n",
    "    input: dataframe, column name.\n",
    "    output: a dict of splited dataframe.\n",
    "    '''\n",
    "    # unique value of column\n",
    "    unique_values = data[col].unique()\n",
    "    # empty dict of dataframe\n",
    "    result_dict = {elem : pd.DataFrame for elem in unique_values}\n",
    "    # split dataframe based on column value\n",
    "    for key in result_dict.keys():\n",
    "        result_dict[key] = data[:][data[col] == key]\n",
    "    return result_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'hot':    humility   outlook temp  windy play\n",
       " 0      high     sunny  hot  FALSE   no\n",
       " 1      high     sunny  hot   TRUE   no\n",
       " 2      high  overcast  hot  FALSE  yes\n",
       " 12   normal  overcast  hot  FALSE  yes,\n",
       " 'mild':    humility   outlook  temp  windy play\n",
       " 3      high     rainy  mild  FALSE  yes\n",
       " 7      high     sunny  mild  FALSE   no\n",
       " 9    normal     rainy  mild  FALSE  yes\n",
       " 10   normal     sunny  mild   TRUE  yes\n",
       " 11     high  overcast  mild   TRUE  yes\n",
       " 13     high     rainy  mild   TRUE   no,\n",
       " 'cool':   humility   outlook  temp  windy play\n",
       " 4   normal     rainy  cool  FALSE  yes\n",
       " 5   normal     rainy  cool   TRUE   no\n",
       " 6   normal  overcast  cool   TRUE  yes\n",
       " 8   normal     sunny  cool  FALSE  yes}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split_dataframe(df, 'temp')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.34285714285714286,\n",
       " 'outlook',\n",
       " {'sunny':    humility outlook  temp  windy play\n",
       "  0      high   sunny   hot  FALSE   no\n",
       "  1      high   sunny   hot   TRUE   no\n",
       "  7      high   sunny  mild  FALSE   no\n",
       "  8    normal   sunny  cool  FALSE  yes\n",
       "  10   normal   sunny  mild   TRUE  yes,\n",
       "  'overcast':    humility   outlook  temp  windy play\n",
       "  2      high  overcast   hot  FALSE  yes\n",
       "  6    normal  overcast  cool   TRUE  yes\n",
       "  11     high  overcast  mild   TRUE  yes\n",
       "  12   normal  overcast   hot  FALSE  yes,\n",
       "  'rainy':    humility outlook  temp  windy play\n",
       "  3      high   rainy  mild  FALSE  yes\n",
       "  4    normal   rainy  cool  FALSE  yes\n",
       "  5    normal   rainy  cool   TRUE   no\n",
       "  9    normal   rainy  mild  FALSE  yes\n",
       "  13     high   rainy  mild   TRUE   no})"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def choose_best_col(df, label):\n",
    "    '''\n",
    "    funtion: choose the best column based on infomation gain.\n",
    "    input: datafram, label\n",
    "    output: max infomation gain, best column, \n",
    "            splited dataframe dict based on best column.\n",
    "    '''\n",
    "    # Calculating label's gini index\n",
    "    gini_D = gini(df[label].tolist())\n",
    "    # columns list except label\n",
    "    cols = [col for col in df.columns if col not in [label]]\n",
    "    # initialize the max infomation gain, best column and best splited dict\n",
    "    min_value, best_col = 999, None\n",
    "    min_splited = None\n",
    "    # split data based on different column\n",
    "    for col in cols:\n",
    "        splited_set = split_dataframe(df, col)\n",
    "        gini_DA = 0\n",
    "        for subset_col, subset in splited_set.items():\n",
    "            # calculating splited dataframe label's gini index\n",
    "            gini_Di = gini(subset[label].tolist())\n",
    "            # calculating gini index of current feature\n",
    "            gini_DA += len(subset)/len(df) * gini_Di\n",
    "        \n",
    "        if gini_DA < min_value:\n",
    "            min_value, best_col = gini_DA, col\n",
    "            min_splited = splited_set\n",
    "    return min_value, best_col, min_splited\n",
    "    \n",
    "choose_best_col(df, 'play')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CartTree:    \n",
    "    # define a Node class\n",
    "    class Node:        \n",
    "        def __init__(self, name):\n",
    "            self.name = name\n",
    "            self.connections = {}    \n",
    "            \n",
    "        def connect(self, label, node):\n",
    "            self.connections[label] = node    \n",
    "        \n",
    "    def __init__(self, data, label):\n",
    "        self.columns = data.columns\n",
    "        self.data = data\n",
    "        self.label = label\n",
    "        self.root = self.Node(\"Root\")    \n",
    "    \n",
    "    # print tree method\n",
    "    def print_tree(self, node, tabs):\n",
    "        print(tabs + node.name)        \n",
    "        for connection, child_node in node.connections.items():\n",
    "            print(tabs + \"\\t\" + \"(\" + connection + \")\")\n",
    "            self.print_tree(child_node, tabs + \"\\t\\t\")    \n",
    "    \n",
    "    def construct_tree(self):\n",
    "        self.construct(self.root, \"\", self.data, self.columns)    \n",
    "    \n",
    "    # construct tree\n",
    "    def construct(self, parent_node, parent_connection_label, input_data, columns):\n",
    "        min_value, best_col, min_splited = choose_best_col(input_data[columns], self.label)   \n",
    "        if not best_col:\n",
    "            node = self.Node(input_data[self.label].iloc[0])\n",
    "            parent_node.connect(parent_connection_label, node)            \n",
    "            return\n",
    "\n",
    "        node = self.Node(best_col)\n",
    "        parent_node.connect(parent_connection_label, node)\n",
    "\n",
    "        new_columns = [col for col in columns if col != best_col]        \n",
    "        # Recursively constructing decision trees\n",
    "        for splited_value, splited_data in min_splited.items():\n",
    "            self.construct(node, splited_value, splited_data, new_columns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root\n",
      "\t()\n",
      "\t\toutlook\n",
      "\t\t\t(sunny)\n",
      "\t\t\t\thumility\n",
      "\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t\t\t(TRUE)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(TRUE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t(overcast)\n",
      "\t\t\t\thumility\n",
      "\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(TRUE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(TRUE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t(rainy)\n",
      "\t\t\t\twindy\n",
      "\t\t\t\t\t(FALSE)\n",
      "\t\t\t\t\t\thumility\n",
      "\t\t\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t(TRUE)\n",
      "\t\t\t\t\t\thumility\n",
      "\t\t\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n"
     ]
    }
   ],
   "source": [
    "tree1 = CartTree(df, 'play')\n",
    "tree1.construct_tree()\n",
    "tree1.print_tree(tree1.root, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
